package pri.zjy.sort;

import java.util.Arrays;

/**
 * @author zhangjy
 * @description 快排
 * @date 2025/3/27 15:07
 */
public class QuickSort {

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] nums = new int[]{8, 1, 3, 9, 0, 3, 5, 2, 7, 6};
        int left = 0, right = nums.length - 1;
        quickSort.quickSort(nums, left, right);
        Arrays.stream(nums).forEach(System.out::println);

    }

    /**
     * 思路：
     * 1.选取一个基准pivot。
     * 2.然后将数组所有 < pivot的元素移动到左边，所有 > pivot的元素移动到右边；从而将原数组分为left和right两个数组。
     * 3.分别对left、right进行上述递归。
     */
    public void quickSort(int[] nums, int left, int right) {
        // 数组只有一个元素，不用再继续快排
        if (left >= right) return;

        // 根据pivot划分数组，并且获取pivot下标
        int pivotIndex = partition(nums, left, right);

        // 对左子表进行快排
        quickSort(nums, left, pivotIndex - 1);
        // 对右子表进行快排
        quickSort(nums, pivotIndex + 1, right);
    }

    private int partition(int[] nums, int low, int high) {
        int pivotIndex = high;
        // 分组并移动
        while (low < high) {
            // 直到左边找到第一个 > pivot的元素
            while (nums[low] <= nums[pivotIndex] && low < high) {
                low++;
            }
            // 直到右边找到第一个 < pivot的元素
            while (nums[high] >= nums[pivotIndex] && low < high) {
                high--;
            }
            // 交换
            swap(nums, low, high);
        }
        // 基准元素与右哨兵交换（此时high是pivot应该放在的位置）
        swap(nums, high, pivotIndex);
        return high;
    }

    private void swap(int[] nums, int first, int second) {
        int tmp = nums[first];
        nums[first] = nums[second];
        nums[second] = tmp;
    }

}
